import java.awt.*;
import java.util.*;
import java.util.List;

public class Wu_5_8 {
    public static void main(String[] args) {
        Vertex first=new Vertex(1);
        Vertex second=new Vertex(2);
        Vertex third=new Vertex(3);
        Vertex fourth=new Vertex(4);
        Vertex fifth=new Vertex(5);
        Vertex sixth=new Vertex(6);

        //初始化图
        Map<Vertex,List<Vertex>> G=new TreeMap<>(); // Vertex and its adjacent list
        List<Vertex> firstTargets=new LinkedList<>();
        firstTargets.add(second);
        firstTargets.add(third);
        G.put(first,firstTargets);
        List<Vertex> secondTargets=new LinkedList<>();
        secondTargets.add(first);
        secondTargets.add(fourth);
        secondTargets.add(fifth);
        G.put(second,secondTargets);
        List<Vertex> thirdTargets=new LinkedList<>();
        thirdTargets.add(first);
        thirdTargets.add(sixth);
        G.put(third,thirdTargets);
        List<Vertex> fourthTargets=new LinkedList<>();
        fourthTargets.add(second);
        G.put(fourth,fourthTargets);
        List<Vertex> fifthTargets=new LinkedList<>();
        fifthTargets.add(second);
        G.put(fifth,fifthTargets);
        List<Vertex> sixthTargets=new LinkedList<>();
        sixthTargets.add(third);
        G.put(sixth,sixthTargets);

        new Wu_5_8().BFS(G,first);

        first.clean();second.clean();third.clean();fourth.clean();fifth.clean();sixth.clean();
        System.out.println();
        new Wu_5_8().DFS(G,first);

    }

    void BFS(Map<Vertex, List<Vertex>> G,Vertex s){
        s.color=Color.gray;
        Queue<Vertex> queue=new LinkedList<>();
        queue.add(s);

        while(!queue.isEmpty()){
            Vertex u=queue.poll();
            System.out.print(u.n+" ");
            //遍历u的邻接列表
            for(Vertex v:G.get(u)){
                if(v.color==Color.white){
                    v.color=Color.gray;
                    queue.add(v);
                }
            }
            u.color=Color.black;
        }

    }
    void DFS(Map<Vertex,List<Vertex>> G,Vertex s){
        s.color=Color.gray;
        Stack<Vertex> stack =new Stack<>();
        stack.add(s);

        while(!stack.isEmpty()){
            Vertex u=stack.pop();
            System.out.print(u.n+" ");
            //遍历u的邻接列表
            for(Vertex v:G.get(u)){
                if(v.color==Color.white){
                    v.color=Color.gray;
                    stack.add(v);
                }
            }
            u.color=Color.black;
        }
    }
}

class Vertex implements Comparable<Vertex>{
    Color color;
    int n;
    public Vertex(int n){
        this.n=n;
        color=Color.white;
    }

    public int compareTo(Vertex o) {
        return this.n-o.n;
    }

    public String toString() {
        return n+"";
    }
    void clean(){
        color=Color.white;
    }
}
